package xiegd.study.leetcode;

/**
 * @Author: xieguangda
 * @Description:
 * @Date: 2023/9/6 10:59
 */
public class Knapsack {
    public int knapSack(int totalWeight, int[] itemWeights, int[] itemValues, int numberOfItems) {
        int i, weight;
        int knapsack[][] = new int[numberOfItems + 1][totalWeight + 1];

        // Build table knapsack[][] in bottom up manner
        for (i = 0; i <= numberOfItems; i++) {
            for (weight = 0; weight <= totalWeight; weight++) {
                if (i == 0 || weight == 0){
                    knapsack[i][weight] = 0;
                }
                else if (itemWeights[i - 1] <= weight){
                    knapsack[i][weight] = Math.max(itemValues[i - 1] + knapsack[i - 1][weight - itemWeights[i - 1]], knapsack[i - 1][weight]);
                }
                else{
                    knapsack[i][weight] = knapsack[i - 1][weight];
                }

            }
        }
        System.out.println("我是测试一看看：" + numberOfItems + "," + totalWeight);
        return knapsack[numberOfItems][totalWeight];
    }

    public static void main(String[] args) {
        int[] itemValues = new int[] { 60, 100, 120 };
        int[] itemWeights = new int[] { 10, 20, 30 };
        int totalWeight = 50;
        int numberOfItems = itemValues.length;
        Knapsack knapsackProblem = new Knapsack();
        System.out.println("最大价值：" + knapsackProblem.knapSack(totalWeight, itemWeights, itemValues, numberOfItems));
    }
}
